from typing import *


# todo 带测试
class segment_tree:

    def __init__(self, origin: List[int]) -> None:
        N = len(origin) + 1
        self.N = N                  # 0位置弃而不用
        self.arr = [0] + origin
        self.sum = [0] * (N * 4)            # 累加和数组 i: l~r累加和
        self.lazy = [0] * (N * 4)           # 拦数组    i: l~r 的值都要累加多少
        self.change = [0] * (N * 4)         # 懒更新数组    i: l~r的值都要变成多少
        self.update = [False] * (N * 4)     # 配合懒更新数组使用，因为上述数组无法确定是变成0，还是没有意义

    def __push_up(self, i: int):
        ''' 计算i位置累加和 '''
        sum[i] = sum[i//2] + sum[i//2+1]

    def __push_down(self, i: int, ln: int, rn: int):
        '''
            往下分发（拦任务，懒更新任务），同时计算左右孩子的值
            i: 当前位置
            ln： 左侧节点数量
            rn： 右侧节点数量
        '''
        l, r = i//2, i//2+1
        # 懒更新优先级高
        if self.update[i]:  # 如果有懒更新, 懒更新分发给左右孩子，
            self.update[l] = self.update[r] = True
            self.change[r] = self.change[r] = self.change[i]
            self.lazy[r] = self.lazy[r] = 0
            self.update[i] = False      # 这个代表有没有懒更新，懒更新的值换不换都一样
            self.sum[l], self.sum[r] = self.change[i] * ln, self.change[i] * rn

        if self.lazy[i]:        # 如果有懒更新信息
            self.lazy[l] = self.lazy[r] = self.lazy[i]
            self.sum[l] = self.sum[l] + self.lazy[i] * ln
            self.sum[r] = self.sum[r] + self.lazy[i] * rn
            self.lazy[i] = 0

    def build(self, l: int, r: int, i: int):
        '''
            l: 我代表的左范围
            r: 我代表的右范围
            i: 当前位置
        '''
        if l == r:  # 叶节点。代表 1~1, 2~2, 3~3 ...
            self.sum[i] = self.arr[l]   # 当前值，等于懒得位置
            return
        mid = (l + r) // 2
        # 左右分发，计算当前
        self.build(l, mid, i // 2)
        self.build(mid + 1, r, i // 2 + 1)
        self.__push_up(i)

    def add(self, L: int, R: int, v: int, l: int, r: int, i: int):
        '''
            L ~ R范围增加 v
            i,l,r : 当前位置，我的左右范围 
        '''
        if l >= L and r <= R:   # 如果包含自己代表的全部范围
            self.lazy[i] += v
            self.sum[i] += v * (r - l + 1)
            return
        # 拦不住，左右分发
        mid = (l + r) // 2
        self.__push_down(i, mid-l-1, r-mid)     # 先结清左右孩子的值
        if L <= mid:    # 如果覆盖到左边，左边分发
            self.add(L, R, v, l, mid, i//2)
        if R > mid:     # 如果覆盖到右边，右边分发
            self.add(L, R, v, mid+1, r, i//2+1)
        self.__push_up(i)   # 最后把自己的sum搞好

    def update(self, L: int, R: int, v: int, l: int, r: int, i: int):
        '''
            L ~ R范围增加 v
            i,l,r : 当前位置，我的左右范围 
        '''
        if l >= L and r <= R:   # 如果包含自己代表的全部范围
            self.update[i] = True
            self.change[i] = v
            self.lazy[i] = 0
            self.sum[i] = v * (r - l + 1)
            return
        # 拦不住，左右分发
        mid = (l + r) // 2
        self.__push_down(i, mid-l-1, r-mid)     # 先结清左右孩子的值
        if L <= mid:    # 如果覆盖到左边，左边分发
            self.update(L, R, v, l, mid, i//2)
        if R > mid:     # 如果覆盖到右边，右边分发
            self.update(L, R, v, mid+1, r, i//2+1)
        self.__push_up(i)   # 最后把自己的sum搞好

    def query(self, L: int, R: int, l: int, r: int, i: int):
        '''
            L ~ R 的累加和为多少
            i,l,r : 当前位置，我的左右范围 
        '''
        if l >= L and r <= R:   # 如果包含自己代表的全部范围
            return sum[i]
        mid = (l + r) // 2
        self.__push_down(i, mid-l-1, r-mid)     # 先结清左右孩子的值
        ans = 0
        if L <= mid:    # 如果覆盖到左边，左边分发
            ans += self.query(L, R, l, mid, i//2)
        if R > mid:     # 如果覆盖到右边，右边分发
            ans += self.query(L, R, mid+1, r, i//2+1)
        # 整个操作是读，没有写。不用更新自己的值了
        return ans